Friendship graph

Friendship graph

The friendship graph F8.
Vertices 2n+1
Edges 3n
Radius 1
Diameter 2
Girth 3
Chromatic number 3
Chromatic index 2n
Properties Unit distance
Planar
Eulerian
factor-critical
Notation Fn

In the mathematical field of graph theory, the friendship graph (or dutch windmill graph or n-fan) Fn is a planar undirected graph with 2n+1 vertices and 3n edges.[1]

The friendship graph Fn can be constructed by joining n copies of the cycle graph C3 with a common vertex.[2]

By construction, the friendship graph Fn is isomorphic to the windmill graph Wd(3,n). It is unit distance with girth 3, diameter 2 and radius 1. The graph F2 is isomorphic to the butterfly graph.

Contents

Friendship theorem

The friendship theorem of Paul Erdős, Alfréd Rényi, and Vera T. Sós (1966)[3] states that the finite graphs with the property that every two vertices have exactly one neighbor in common are exactly the friendship graphs. Informally, if a group of people has the property that every pair of people has exactly a friend in common, then there must be one person who is a friend to all the others. However, for infinite graphs, there can be many different graphs with the same cardinality that have this property.[4]

Labeling and colouring

The friendship graph has chromatic number 3 and chromatic index 2n. Its chromatic polynomial can be deduced from the chromatic polynomial of the cycle graph C3 and is equal to (x-2)^n (x-1)^n x.

The friendship graph Fn is edge-graceful if and only if n is odd. It is graceful if and only if n ≡ 0 (mod 4) or n ≡ 1 (mod 4).[5][6]

Every friendship graph is factor-critical.

Extremal graph theory

According to extremal graph theory, every graph with sufficiently many edges (relative to its number of vertices) must contain a k-fan. More specifically, this is true for an n-vertex graph if the number of edges is

\left\lfloor \frac{n^2}{4}\right\rfloor %2B f(k),

where f(k) is k2 − k if k is odd, and f(k) is k2 − 3k/2 if k is even. These bounds generalize Turán's theorem on the number of edges in a triangle-free graph, and they are the best possible bounds for this problem, in that for any smaller number of edges there exist graphs that do not contain a k-fan.[7]

Gallery


References

  1. ^ Weisstein, Eric W., "Dutch Windmill Graph" from MathWorld.
  2. ^ Gallian, J. A. "Dynamic Survey DS6: Graph Labeling." Electronic J. Combinatorics, DS6, 1-58, Jan. 3, 2007. [1].
  3. ^ Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), "On a problem of graph theory", Studia Sci. Math. Hungar. 1: 215–235, http://www.renyi.hu/~p_erdos/1966-06.pdf .
  4. ^ Chvátal, Václav; Kotzig, Anton; Rosenberg, Ivo G.; Davies, Roy O. (1976), "There are \scriptstyle 2^{\aleph_\alpha} friendship graphs of cardinal \scriptstyle\aleph_\alpha", Canadian Mathematical Bulletin 19 (4): 431–433 .
  5. ^ J.C. Bermond, A. E. Brouwer, and A. Germa, "Systèmes de triplets et différences associées", Problèmes Combinatoires et Théorie des Graphes, Colloq. Intern. du CNRS, 260, Editions du Centre Nationale de la Recherche Scientifique, Paris (1978) 35-38.
  6. ^ J. C. Bermond, A. Kotzig, and J. Turgeon, On a combinatorial problem of antennas in radioastronomy, in Combinatorics, A. Hajnal and V. T. Sos, eds., Colloq. Math. Soc. Janos Bolyai, 18, 2 vols. North-Holland, Amsterdam (1978) 135-149.
  7. ^ Erdős, P.; Füredi, Z.; Gould, R. J.; Gunderson, D. S. (1995), "Extremal graphs for intersecting triangles", Journal of Combinatorial Theory, Series B 64 (1): 89–100, doi:10.1006/jctb.1995.1026, MR1328293, http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_erdos_gould_gunderson_triangles.ps .